home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_10_04 / 1004018a < prev    next >
Encoding:
Text File  |  1992-03-03  |  1.6 KB  |  73 lines
  1. /* qsort function */
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5.         /* macros */
  6. #define MAX_BUF    256        /* chunk to copy on swap */
  7.  
  8. void (qsort)(void *base, size_t n, size_t size, _Cmpfun *cmp)
  9.     {    /* sort (char base[size])[n] using quicksort */
  10.     while (1 < n)
  11.         {    /* worth sorting */
  12.         size_t i = 0;
  13.         size_t j = n - 1;
  14.         char *qi = (char *)base;
  15.         char *qj = qi + size * j;
  16.         char *qp = qj;
  17.  
  18.         while (i < j)
  19.             {    /* partition about pivot */
  20.             while (i < j && (*cmp)(qi, qp) <= 0)
  21.                 ++i, qi += size;
  22.             while (i < j && (*cmp)(qp, qj) <= 0)
  23.                 --j, qj -= size;
  24.             if (i < j)
  25.                 {    /* swap elements i and j */
  26.                 char buf[MAX_BUF];
  27.                 char *q1 = qi;
  28.                 char *q2 = qj;
  29.                 size_t m, ms;
  30.  
  31.                 for (ms = size; 0 < ms;
  32.                     ms -= m, q1 += m, q2 -= m)
  33.                     {    /* swap as many as possible */
  34.                     m = ms < sizeof (buf) ? ms : sizeof (buf);
  35.                     memcpy(buf, q1, m);
  36.                     memcpy(q1, q2, m);
  37.                     memcpy(q2, buf, m);
  38.                     }
  39.                 ++i, qi += size;
  40.                 }
  41.             }
  42.         if (qi != qp)
  43.             {    /* swap elements i and pivot */
  44.             char buf[MAX_BUF];
  45.             char *q1 = qi;
  46.             char *q2 = qp;
  47.             size_t m, ms;
  48.  
  49.             for (ms = size; 0 < ms; ms -= m, q1 += m, q2 -= m)
  50.                 {    /* swap as many as possible */
  51.                 m = ms < sizeof (buf) ? ms : sizeof (buf);
  52.                 memcpy(buf, q1, m);
  53.                 memcpy(q1, q2, m);
  54.                 memcpy(q2, buf, m);
  55.                 }
  56.             }
  57.         j = n - i - 1, qi += size;
  58.         if (j < i)
  59.             {    /* recurse on smaller partition */
  60.             if (1 < j)
  61.                 qsort(qi, j, size, cmp);
  62.             n = i;
  63.             }
  64.         else
  65.             {    /* lower partition is smaller */
  66.             if (1 < i)
  67.                 qsort(base, i, size, cmp);
  68.             base = qi;
  69.             n = j;
  70.             }
  71.         }
  72.     }
  73.